'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-06-25 11:44:49
'''
'''
139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
'''
from typing import List
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False]*(len(s)+1) #注意边界，比s长一个，存贮边界为True，逻辑统一
        dp[0] = True
        if not wordDict:
            return False
        wordDict = set(wordDict)
        l = max([len(i) for i in wordDict])
        for i, test in enumerate(dp):
            for j in range(1, min(i+1, l+1)):
                # 转移方程，当前的i-1脚标str字符串是否可以被词典中的词构成，
                # 取决于之前一部分与中间差值字符串是否再词典中。
                dp[i] |= (dp[i-j] & (s[i-j: i] in wordDict))
        return dp[-1]

if __name__ == "__main__":
    solution = Solution()
    s='leetcode'
    wordDict = ['leet', 'code']
    print(solution.wordBreak(s, wordDict))